from typing import List


class Solution:
    def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]:

        to = ((0, 1), (1, 0), (-1, 0), (0, -1))

        # def arrive(x, y):
            # return x < 0 or y < 0 or x >= m or y >= n

        def arrivePacific(x,y):
            return x <0 or y< 0

        def arriveAlantic(x,y):
            return x >=m or y >=n

        def backtrack(x, y, visited):
            nonlocal ta, tp
            # print(x, y)
            # print(visited)
            for i in to:
                new_x = i[0] + x
                new_y = i[1] + y
                if arriveAlantic(new_x, new_y):
                    ta = True
                    continue
                if arrivePacific(new_x, new_y):
                    tp = True
                    continue
                if ta == True and tp == True:
                    return
                if [new_x, new_y] in ans:
                    return True
                if matrix[new_x][new_y] <= matrix[x][y] and [new_x, new_y] not in visited:
                    backtrack(new_x, new_y, visited + [[new_x, new_y]])
                
                

        m = len(matrix)
        if not m:
            return []
        n = len(matrix[0])
        
        ta = tp = False
        ans = []  # List[List[int]]
        for i in range(m):
            for j in range(n):
                ta = tp = False
                backtrack(i, j, [])
                if ta == True and tp == True:
                    ans.append([i, j])

        return ans


if __name__ == "__main__":
    matrix = [[1, 2, 2, 3, 5], [3, 2, 3, 4, 4], [
         2, 4, 5, 3, 1], [6, 7, 1, 4, 5], [5, 1, 1, 2, 4]]
    # matrix = [[0,0,0], [0,3,0], [0,0,0]]
    res = Solution().pacificAtlantic(matrix)
    print(res)
    # == [ [0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]
